The present invention relates to an adder, and more particularly to a parallel adder.
A high-speed parallel adder is frequently used within a high-speed digital signal processor. However, since increased speed requires greater chip area faster speeds result in such disadvantages as a complicated layout and increased chip area.
A known algorithm for binary addition, expressed in terms of Boolean algebra, is as follows. EQU C.sub.i =G.sub.i +P.sub.i.G.sub.i-1 EQU P.sub.i =A.sub.i +B.sub.i EQU G.sub.i =A.sub.i.B.sub.i EQU S.sub.i =G.sub.i-1 +P.sub.i
where C.sub.i is the carry signal from a bit position i, P.sub.i is a block carry propagating signal, G.sub.i is a block carry generating signal, S.sub.i is a final output, A is an addend, and B is an augend.
A new operator "o" having the following function may be defined as: (g, p) o (g', p')=(g+(po.g'), p.p') where g, p, g' and p' are Boolean variables. The new operator is associative, and a carry signal is determined by C.sub.i =G.sub.i. Here, (G.sub.i, P.sub.i)=(g.sub.i, p.sub.i) if i=1 and (gi,pi) o (g.sub.i-1,P.sub.i-1)=(g.sub.i,P.sub.i) o (g.sub.i-1,P.sub.i-1) . . . o . . . (g.sub.1,p.sub.1) if 2.ltoreq.i.ltoreq.n.
The associative characteristic of operator "o" is formed of elements (G.sub.i, P.sub.i) having a binary tree structure with a path length of (log n).
FIG. 1 illustrates a block diagram of general adder for performing the above-described algorithm including the logic gates needed for each block operation.
The circuit shown in FIG. 1 includes a carry generation & propagation block 1, a carry evaluation block 2 for evaluating the carry by inputting signals from carry generation & propagation block 1, and a sum block 3 for inputting signals from carry evaluation block 2 to thereby output a final sum.
Carry generation & propagation block 1 is composed of AND gates 4.sub.n -4.sub.1 for inputting two numbers A.sub.i and B.sub.i (where i=1, 2, 3 . . . , n) to generate the carry, and XOR gates 5.sub.n -5.sub.1 for inputting two numbers A.sub.i and B.sub.i (where i=1, 2, 3 . . . , n) to propagate the carry.
Sum block 3 is composed of XOR gates 6.sub.n -6.sub.1, each of which input the carry generating signal P.sub.i (where i=1, 2, 3 . . . , n) and output signal C.sub.i (where i=1, 2, 3 . . . , n) of carry evaluation block 2, to thereby output the result of the summation.
FIG. 2 illustrates a tree structure of the carry evaluating block shown in FIG. 1.
In FIG. 2, a solid dot designates an operation whereby two input signals (gin.sub.i-1, pin.sub.i-1) and (gin.sub.i, pin.sub.i) are input to thereby generate: EQU gout=gin.sub.i-1 V(pin.sub.i-1 .LAMBDA.gin.sub.i)
and EQU pout=pin.sub.i-1 A pin.sub.i ( 1)
Also, a small circle designates an operation whereby two input signals gin and pin are input to generate: EQU gout=gin
and EQU pout=pin (2)
That is, in the case of the 16-bit adder shown in FIG. 2, the computation is carried out through eight stages.
The tree structure shown in FIG. 2 will be described below.
In a first stage (T=0), the operation of equation (2) is performed by inputting the carry generating and propagating signals (g.sub.i, p.sub.i where i=1, 2, 3 . . . , n) by means of sixteen operations, each represented by the small circles.
In a second stage (T=1), the operation of equation (1) is performed by inputting respective odd output signals (g.sub.i, p.sub.i where i=1, 3, 5 . . . , 15) and even output signals g.sub.i and p.sub.i (where i=2, 4, 6 . . . . , 16) while also allowing the odd output signals to be passed intact.
In a third stage (T=2), the operation of equation (1) is performed by inputting respective output signals of the even solid dots from the second stage (T=1) and the immediatelly lower odd solid dot from the second stage (T=1), while also allowing the odd output signals and the output signals of the odd solid dots of the second stage (T=1) to be passed intact.
In a fourth stage (T=3), the operation of equation (1) is performed by inputting the output signals of the solid dot in third stage (T=2) by twos, while also allowing the output signals of the small circles and the odd solid dots in third stage (T=2) to be passed intact.
In a fifth stage (T=4). the operation of equation (1) is performed by inputting the output signals of the two solid dots in fourth stage (T=3), while allowing the output signals of the small circle and the odd solid dot in the fourth stage (T=3) to be passed intact.
In a sixth stage (T=S), the operation of equation (1) is performed by inputting the eighth and twelfth output signals of the small circle in fifth stage (T=4), while allowing all output signals other than the twelfth output signal (both solid dots and small circles) of the fifth stage to pass intact.
In a seventh stage (T=6), the operation of equation (1) is performed by inputting the fourth and sixth output signals, eighth and tenth output signals, and twelfth and fourteenth output signals in sixth stage (T=S), while allowing the output signals other than the sixth, tenth and fourteenth output signals to pass intact.
In an eighth stage (T=7), the operation of equation (1) is performed by inputting the second & third, fourth & fifth, sixth & seventh, eighth & ninth, tenth & eleventh, twelfth & thirteenth, and fourteenth & fifteenth output signals in seventh stage (T=6), and the remaining even output signals and first output signal are passed intact. By performing the above-described operations, a final result C.sub.i (where i=1, 2, 3 . . . , 16) is output.
As is apparent, the conventional parallel adder has a slow operating speed and requires complicated circuitry.